package main.Q301_400;

import java.util.*;

public class Q361_370 {
    public static void main(String[] args) {
        System.out.println(4%8);
        System.out.println("Question361：");
        System.out.println("Question362：");
        System.out.println("Question363：");
        System.out.println("Question364：");
        System.out.println("Question365：水壶问题");
        System.out.println("Question366：");
        System.out.println("Question367：有效的完全平方数");
        System.out.println("Question368：最大整除子集");
        System.out.println("Question369：");
        System.out.println("Question370：");
    }
}

class Question365{
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        Set<Integer> set=new HashSet<>();
        int cha=Math.abs(jug2Capacity-jug1Capacity);
        set.add(jug1Capacity);
        set.add(jug2Capacity);
        set.add(jug2Capacity+jug1Capacity);
        set.add(cha);
        set.add(jug1Capacity+cha);
        set.add(jug2Capacity+cha);
        if (set.contains(targetCapacity)) return true;
        return false;
    }
}

class Question367{
    public static boolean isPerfectSquare(int num) {//二分法
        int left = 0, right = num;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            long square = (long) mid * mid;
            if (square < num) {
                left = mid + 1;
            } else if (square > num) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

class Question368{
    public static List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        List<Integer> list=new ArrayList<>();
        int length= nums.length,maxSize=0;
        List<List<Integer>> buckets=new ArrayList<>();
        for (int i=0;i<length;i++){//将能被num[i]整除的数放在桶中
            List<Integer> tempBucket=new ArrayList<>();
            int bucketIndex=-1,bucketSize=0;//第i个桶之前能被i整除的桶最多元素的桶
            for (int j=0;j<i;j++){//确定前i个桶中能被i整除且元素最多的桶
                if (nums[i]%nums[j]==0&&buckets.get(j).size()>bucketSize){
                    bucketIndex=j;
                    bucketSize=buckets.get(j).size();
                }
            }
            if (bucketIndex!=-1) tempBucket.addAll(buckets.get(bucketIndex));
            tempBucket.add(nums[i]);//加上自身
            maxSize=Math.max(maxSize,tempBucket.size());
            buckets.add(tempBucket);
        }
        for (List<Integer> temp:buckets){
            if (temp.size()==maxSize){
                list=temp;
                break;
            }
        }
        return list;
    }
}